package uestc.lj.advanced.sort;

/**
 * @Author:Crazlee
 * @Date:2021/12/6
 */
public class Code01_MaxGap {
	public static int maxGap(int[] nums) {
		if (nums == null || nums.length < 2) {
			return 0;
		}
		int length = nums.length;
		int min = Integer.MAX_VALUE;
		int max = Integer.MIN_VALUE;
		for (int num : nums) {
			min = Math.min(num, min);
			max = Math.max(num, max);
		}
		if (min == max) {
			return 0;
		}
		//利用桶排序
		boolean[] hasNum = new boolean[length + 1];
		// maxs[i]代表i号桶收集的所有数字的最大值
		int[] maxs = new int[length + 1];
		// mins[i]代表i号桶收集的所有数字的最小值
		int[] mins = new int[length + 1];

		int bid = 0;
		for (int num : nums) {
			//将num放入对应的桶中
			bid = bucket(num, length, min, max);
			mins[bid] = hasNum[bid] ? Math.min(mins[bid], min) : num;
			maxs[bid] = hasNum[bid] ? Math.max(maxs[bid], max) : num;
			hasNum[bid] = true;
		}

		int res = 0;
		int lastMax = maxs[0];
		int i = 1;
		for (; i <= length; i++) {
			if (hasNum[i]) {
				res = Math.max(res, mins[i] - lastMax);
				lastMax = maxs[i];
			}
		}
		return res;
	}

	public static int bucket(long num, long len, long min, long max) {
		return (int) ((num - min) * len / (max - min));
	}

}
